package com.qrpcw.algorithms;
import java.util.Arrays;

public class HeapSort {

	public static void main(String[] args) {
		HeapSort sort = new HeapSort();
		int[] a = new int[]{16,14,10,8,7,9,3,2,4,1};  //16,14,10,8,7,9,3,2,4,1
		sort.heapSort(a);
		System.out.println(Arrays.toString(a));
	}
	
	//private int parent(int i){ return (i-1)/2; }
	private int left(int i){ return 2*i+1; } //leftChild position
	private int right(int i){ return 2*i+2; } //rightChild position

	public void exchange(int[] A, int i,int j){
		int temp;
		temp = A[i]; 
		A[i] = A[j]; 
		A[j] = temp;
	}
	
	public void maxHeapify(int[] A, int i, int heapSize){
		int l = left(i);  //l=leftChild   i=root
		int r = right(i); //r=rightChild
		int largest;
		if( l < heapSize && A[l] > A[i] ){
			largest = l;
		}else{
			largest = i;
		}
		if( r < heapSize && A[r] > A[largest] ){
			largest = r;
		}
		if(largest != i){
			exchange(A,i,largest); //exchange child with root
			maxHeapify(A,largest,heapSize);
		}
	}
	
	public void buildMaxHeap(int[] A){
		int heapSize = A.length;
		for(int i = (A.length/2)-1; i>=0; i--){
			maxHeapify(A,i,heapSize);
		}
	}
	
	public void heapSort(int[] A){
		int heapSize = A.length;
		buildMaxHeap(A);
		System.out.println(Arrays.toString(A));
		for(int i = A.length-1; i>=1; i--){
			exchange(A,0,i);
			heapSize = heapSize - 1;
			maxHeapify(A, 0, heapSize);
		}
	}
}
